import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

class MinStack {

    private Stack<Integer> s1;
    private Stack<Integer> s2;

    public MinStack() {
        s1=new Stack<>();
        s2=new Stack<>();
    }

    public void push(int val) {
        if (s1.empty()||val<=s2.peek()){
            s2.push(val);
        }
        s1.push(val);
    }

    public void pop() {
        if(s1.peek().equals(s2.peek())){
            s2.pop();
        }
        s1.pop();
    }

    public int top() {
        return s1.peek();
    }

    public int getMin() {
        return s2.peek();
    }
}

class Solution{
    public boolean IsPopOrder (int[] pushV, int[] popV) {
        Stack<Integer> stack=new Stack<>();
        int sh=0;
        int op=0;
        while(sh<pushV.length){
            stack.push(pushV[sh++]);

            while(!stack.empty()&&op< popV.length&&stack.peek().equals(popV[op])){
                stack.pop();
                ++op;
            }
        }
        return stack.empty();
    }
}


class MyCircularQueue {

    private int[] num;
    private int front;
    private int tail;
    private int cap;

    public MyCircularQueue(int k) {
        cap=k+1;
        num=new int[cap];
        front=tail=0;
    }

    public boolean enQueue(int value) {
        if (isFull())
            return false;
        num[tail]=value;
        tail=(tail+1)%cap;
        return true;
    }

    public boolean deQueue() {
        if(isEmpty())
            return false;
        front=(front+1)%cap;
        return true;
    }

    public int Front() {
        if (isEmpty())
            return -1;
        return num[front];
    }

    public int Rear() {
        if (isEmpty())
            return -1;
        if(tail==0)
            return num[cap-1];
        return num[tail-1];
    }

    public boolean isEmpty() {
        return front==tail;
    }

    public boolean isFull() {
        return (tail+1)%cap==front;
    }
}


class MyQueue {

    private Stack<Integer> scome;
    private Stack<Integer> sgo;

    public MyQueue() {
        scome=new Stack<>();
        sgo=new Stack<>();
    }

    public void push(int x) {
        scome.push(x);
    }

    public int pop() {
        if (sgo.empty()){
            while(!scome.empty()){
                sgo.push(scome.pop());
            }
        }
        return sgo.pop();
    }

    public int peek() {
        if (sgo.empty()){
            while(!scome.empty()){
                sgo.push(scome.pop());
            }
        }
        return sgo.peek();
    }

    public boolean empty() {
        return scome.empty()&&sgo.empty();
    }
}



class MyStack {

    private Queue<Integer> q1;
    private Queue<Integer> q2;

    public MyStack() {
        q1=new LinkedList<>();
        q2=new LinkedList<>();
    }

    public void push(int x) {
        if (q1.isEmpty()){
            q2.add(x);
        }else {
            q1.add(x);
        }
    }

    public int pop() {
        int tep=0;
        if (q1.isEmpty()){
            while (!q2.isEmpty()){
                tep=q2.remove();
                if (!q2.isEmpty()){
                    q1.add(tep);
                }
            }
        }else {
            while (!q1.isEmpty()){
                tep=q1.remove();
                if (!q1.isEmpty()){
                    q2.add(tep);
                }
            }
        }
        return tep;
    }

    public int top() {
        int tep=0;
        if (q1.isEmpty()){
            while (!q2.isEmpty()){
                tep=q2.remove();
                q1.add(tep);
            }
        }else {
            while (!q1.isEmpty()){
                tep=q1.remove();
                q2.add(tep);
            }
        }
        return tep;
    }

    public boolean empty() {
        return q1.isEmpty()&&q2.isEmpty();
    }
}






public class Test1 {
    public static void main(String[] args) {
        MyCircularQueue myCircularQueue=new MyCircularQueue(6);
        System.out.println(myCircularQueue.enQueue(6));
        System.out.println(myCircularQueue.Rear());
        System.out.println(myCircularQueue.Rear());
        System.out.println(myCircularQueue.deQueue());
        System.out.println(myCircularQueue.enQueue(5));
        System.out.println(myCircularQueue.Rear());
        System.out.println(myCircularQueue.deQueue());
        System.out.println(myCircularQueue.Front());
        System.out.println(myCircularQueue.deQueue());
        System.out.println(myCircularQueue.deQueue());
        System.out.println(myCircularQueue.deQueue());

    }



    public static void main1(String[] args) {
        MinStack minStack=new MinStack();
        minStack.push(512);
        minStack.push(-1024);
        minStack.push(-1024);
        minStack.push(512);

        minStack.pop();
        System.out.println(minStack.getMin());
        minStack.pop();
        System.out.println(minStack.getMin());
        minStack.pop();
        System.out.println(minStack.getMin());
    }

}
